#pragma once
#include<iostream>
#include<vector>

using namespace std;

namespace My
{
	template <class T, class Container = vector<T>, class Compare = less<T> >
	class priority_queue
	{
	public:
		priority_queue()
		{}

		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				_v.push_back(*first);
				first++;
			}

			for (int i = (_v.size() - 2) / 2; i >= 0; i--)
			{
				adjust_down(i);
			}
		}

		void adjust_up(size_t child)
		{
			size_t parent = (child - 1 )/ 2;
			while (child>0)
			{
				if (_comp(_v[parent], _v[child]))
				{
					swap(_v[parent],_v[child]);
					child=parent;
					parent =(child - 1)/2;
				}
				else
				{
					break;
				}
			}
		}

		void adjust_down(size_t parent)
		{
			size_t child = (parent * 2) + 1;
			while (child < _v.size())
			{
				if (child + 1 < _v.size() && _comp(_v[child], _v[child + 1]))
				{
					child++;
				}
				if (_comp(_v[parent], _v[child]))
				{
					swap(_v[parent], _v[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		bool empty() const
		{
			return _v.empty();
		}

		size_t size() const
		{
			return _v.size();
		}
		const T& top() const
		{
			return _v[0];
		}
		void push(const T& x)
		{
			_v.push_back(x);
			adjust_up(_v.size() - 1);
		}
		void pop()
		{
			swap(_v[_v.size() - 1], _v[0]);
			_v.pop_back();
			adjust_down(0);
		}

	private:
		Container _v;
		Compare _comp;
	};


	void test01()
	{
	vector<int> v1= { 1,3,4,5,8,10,12 };
	priority_queue<int> q1(v1.begin(), v1.end());
	priority_queue<int, vector<int>, greater<int>> q2(v1.begin(), v1.end());

	while(!q1.empty())
	{
		cout << q1.top() << ' ';
		q1.pop();
	}
	cout << endl;

	while (!q2.empty())
	{
		cout << q2.top() << ' ';
		q2.pop();
	}
	cout << endl;

	}
}